package bab;

import java.util.LinkedList;
import java.util.Set;
import java.util.TreeSet;

/**
 * Algo trouvé sur internet qui semble ne pas toujours retourné la solution maximum !
 */

/**
 * 
 * @author Marek Grzes, University of Waterloo, 2011.
 * @version last modified 30/03/2011
 *
 */

/**
 * This is for 0-1 knapsack problem. The fractional knapsack problem
 * can be solved using the greedy algorithm (see Cormen pp. 425).
 */
public class Knapsack {
	
	/// Prints table V
	public static void printV(int[][] tab, String message) {
		System.out.println("---------- [" + message + "]");
		System.out.print("      \t");
		for ( int w=0; w < tab[0].length; w++ ) {
			System.out.print("w=" + w + "\t");
		}
		System.out.println();
		for ( int i=0; i < tab.length; i++ ) {
			System.out.print("item"+i+"\t");
			for ( int w=0; w < tab[0].length; w++ ) {
				System.out.print(tab[i][w]+"\t");
			}
			System.out.println();
		}
		System.out.println("----------");
	}
	private int weight;
	private int maxValue;
	private Set<Integer> solution;
	
	public Knapsack(Data data) {
		// define items here
		int[] vi = data.getProfits();
		int[] wi = data.getWeights();
		int n = vi.length;
		// set capacity
		int W = data.getCapacity();

		// V[i, capacity w] will store the maximum combined value of any any subset of items {0,1,...,i} of combined size at most w.
		int[][] V = new int[n][W+1];
		boolean[][] keep = new boolean[n][W+1];
		for ( int i = 0; i < n; i++ ) {
			for ( int w=0; w <= W; w++ ) {
				keep[i][w] = false;
			}
		}
		
		// the main algorithm starts here
		// (1) first compute maximum value for all w<W when only first item 0 can be taken
		for ( int w = 0; w <= W; w++ ) {
			if ( wi[0] <= w) {
				V[0][w] = wi[0];
				keep[0][w] = true;	// set true, which means that item 0 can be taken when left capacity is exactly w
			} else {
				V[0][w] = 0;
			}
		}
		//printV(V, "maximum value V, for all w<W, when only item 0 can be taken");
		// (2) then compute maximum value for all w<W when any subset of items 0-i can be taken
		for ( int i = 1; i < n; i++ ) {
			for ( int w = 0; w <= W; w++) {
				if ( wi[i] <= w && vi[i] + V[i-1][w-wi[i]] > V[i-1][w] ) {
					V[i][w] = vi[i] + V[i-1][w-wi[i]];
					keep[i][w] = true; // set true, which means that item i can be taken when left capacity is exactly w
				} else {
					V[i][w] = V[i-1][w];
				}
			}
			//printV(V, "maximum value V, for all W, when optimal subset of items 0 to " + i + " can be taken");
		}
		
		this.solution = new TreeSet<>();
		// print the result
		int K = W;
		int wsel = 0;
		int vsel = 0;
		for ( int i = n - 1 ; i >= 0; i-- ) { // need to go in the reverse order
			if ( keep[i][K] == true) {
				solution.add(i);
				wsel += wi[i];
				vsel += vi[i];
				K = K - wi[i];
			}
		}

		this.maxValue = vsel;
		this.weight = wsel;
	}

	public int getWeight() {
		return weight;
	}

	public int getMaxValue() {
		return maxValue;
	}

	public Set<Integer> getSolution() {
		return solution;
	}

	

}